package com.xcoder.algorithm.sort;

/**
 * 归并排序
 * <p>
 * 网上普遍解法: https://blog.csdn.net/m0_38056893/article/details/79461901
 */
public class MergeSort {

    // 辅助Array，备份数组左半部分
    private static int[] leftArr;

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 1, 2, 3, 0};
//        int[] a = {2, 1, 4, 0, 12, 32, 2, 9, 5, 3, 12, 14};
        leftArr = new int[(a.length + 1) >> 1]; // 如果是奇数个左半部分多分一个
        mergeSort(a, 0, a.length - 1);
        System.out.print("排序结果：");
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    private static void mergeSort(int[] a, int start, int end) {
        if (start < end) {
            // 分，这里不要(begin + end) >> 1，因为加起来可能超过int最大范围
            int mid = start + ((end - start) >> 1);
            // 治
            mergeSort(a, start, mid);
            mergeSort(a, mid + 1, end);
            // 合
            merge(a, start, mid, end);
        }
    }

    private static void merge(int[] a, int begin, int mid, int end) {
        int li = 0, le = mid - begin; // 左半部分数组
        int ri = mid + 1, re = end; // 右半部分
        int ai = begin;
        // 拷贝左半部分到辅助数组
        for (int i = li; i <= le; i++) {
            leftArr[i] = a[begin + i];
        }
        while (li <= le) {
            // 如果右边小用右边的，如果等于还是用左边的，保证稳定性
            if (ri <= re && a[ri] < leftArr[li]) {
                a[ai++] = a[ri++];
            } else {
                a[ai++] = leftArr[li++];
            }
        }
    }
}
